/**
 * 判断链表中是否有环
 */
public class RingListChecker {

    public static boolean hasRing(Node head) {

        if (head == null) return false;

        // 定义快慢两个指针，当它们重合时，则有环，否则无环
        Node fast = head.getNext();  // 快指针，步长为2
        Node slow = head;  // 慢指针，步长为1

        while(fast != null && fast.getNext() != null) {

            // fast绕了一圈后碰到slow了，有环
            if (fast == slow) return true;

            // 两个指针继续遍历
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        }

        // fast遍历结束，说明无环
        return false;
    }

    public static void main(String[] args) {

        Node head = null;
        Node temp = null;
        int length = 10;
        for (int i = 1; i <= length; i++) {
            Node node = new Node(i);
            if (i == 1) {
                head = node;
            } else {
                temp.setNext(node);
            }
            temp = node;
            if (i == length) temp.setNext(head); // 把最后一个结点指向头结点
        }

        System.out.println(hasRing(head));
    }
}
